package LeetCode.exercise;

import java.util.ArrayList;
import java.util.List;

public class LC47 {
    List<List<Integer>> lists = new ArrayList<>();
    List<Integer> tmp = new ArrayList<>();
    boolean[] flag;
    public List<List<Integer>> permuteUnique(int[] nums) {

        flag = new boolean[nums.length];
        bfs(nums, 0);
        return lists;
    }

    public void bfs(int[] nums, int cur){
        if(tmp.size() == nums.length){
            if(!lists.contains(tmp)){
                lists.add(new ArrayList<>(tmp));
            }
            return;
        }
        for(int i = 0; i < nums.length; i++){
            if(!flag[i]){
                tmp.add(nums[i]);
                flag[i] = true;
                bfs(nums, i+1);
                flag[i] = false;
                tmp.remove(tmp.size()-1);
            }
        }
    }

    public static void main(String[] args) {
        LC47 lc47 = new LC47();
        int[] nums = {1, 1, 2};
        System.out.println(lc47.permuteUnique(nums));
    }
}
